package com.lines.chap01;

/**
 * <p>
 * <code>BigO</code>
 * </p>
 *
 * @author junbao3
 * TODO
 * @date 2023-03-21 15:20
 * Copyright (C) 2021 IFlyTek. All rights reserved.
 */
public class BigO {
    public static void main(String[] args) {
        int a = 1;  //1次 O（1）

        for (int i = 0; i < 3; i++) {//这里运行几次？4次 在第4次的时候结束 跳出i=3
            a = a + 1; //这里运行几次？3次  时间复杂度：o(1)
        }

        int n = Integer.MAX_VALUE;//n表示未知
        int i = 1;
        while(i<=n){
            i = i *2;//执行多少次?
        }
        while(i<=n){
            i = i *3;//执行多少次? 还是o(logn)
        }
        // i的值 2 4 8 16 32 => 2^0 2^1 2^2 ...2^n
        //运行一次  i=2 2^1
        //运行2次 i=4 2^2
        //运行x次 退出 i = 2^x  i<=n
        // ==> 2^x = n 求出x就是我们运行的次数 x= log2n==>计算机忽略掉参数 x=logn==>o(logn)
        //二分查找为什么是logn的算法
        //1~100 找69这个数
        //50  (1+100)/2 = 50  二分查找还会详细计算


        for (int j = 0; j < n; j++) {
            while(i<=n){
                i = i *2;//执行多少次? nlogn
            }
        }

        for (int j = 0; j < n; j++) {
            a = a +1; // 运行了多少次？ O(n) n一定是一个未知的 如果n是已知的变量 那就是O(1)
            //数据库查询的数量不确定，可以用n代表
        }

        for (int j = 0; j < n; j++) { //n次
            for (int k = 0; k < n; k++) {//n次
                a = a+1;//运行了多少次 O(n^2)
            }

        }

        //冒泡排序
        int temp  = 0 ;
        int[] arr = {18,13,50,15,4,17,18};
        for(int i1 = 0 ;i1< arr.length -1; i1++){
            for(int j = 0; j<arr.length-1-i1; j++){
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

        }

        /*
        外层循环  n次 O(n)
        内层循环
        外面是1 2     n
        里面是n n-1   1  里面总共运行多少次 1+2+3...+n  (n*(n+1))/2   ==>n^2 有加减法的时候，找次数最高的


        */
    }
}
